class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return qsort(nums,0,nums.size()-1,k);
    }
    int qsort(vector<int>&nums,int begin,int end,int k)
    {
        if(begin==end)return nums[begin];
        int key=getRom(nums,begin,end);
        int i=begin,left=begin-1,right=end+1;
        while(i<right)
        {
            if(nums[i]<key)swap(nums[++left],nums[i++]);
            else if(nums[i]==key)i++;
            else swap(nums[--right],nums[i]);
        }
        int c=end-right+1;
        int b=right-left-1;
        if(c>=k)return qsort(nums,right,end,k);
        else if(b+c>=k)return key;
        else return qsort(nums,begin,left,k-b-c);
    }
    int getRom(vector<int>& nums,int begin,int end)
    {
        return nums[rand()%(end-begin+1)+begin];
    }
};
